﻿using System;
using System.Collections.Generic;
using System.Text;

namespace DataStructureSample.Sorts
{
    public class InsertSort
    {
        public static int[] Sort(int[] arr)
        {
            for (int i = 1; i < arr.Length; i++)
            {
                var temp = arr[i];
                var inserted = false;
                for (int j = i-1; j >=0; j--)
                {
                    if (arr[j]>temp)
                    {
                        arr[j + 1] = arr[j];
                    }
                    else
                    {
                        arr[j + 1] = temp;
                        inserted = true;
                        break;
                    }
                }
                if (!inserted)
                {
                    arr[0] = temp;
                }
            }
            return arr;
        }
    }
}
